//
// Created by DengLibin on 2019/1/8 0008.
//

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <cstring>
using namespace std;

int max(int x, int y){
    return x > y ? x : y;
}
/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 */
int lengthOfLongestSubstring(string s) {
    int res = 0, left =0, right = 0;//三个变量,返回结果，子串的左边界，子串的右边界
    set<char> tempSet;//set集合代表滑动窗口
    while (right < s.length()){
        if(tempSet.find(s[right]) == tempSet.end()){ //滑动窗口不包含右边界字符
            tempSet.insert(s[right]); //直接把右边界字符加到滑动窗口中
            right++; //边界右移一位
            res = max(res, tempSet.size());
        }else{ //滑动窗口包含右边界的字符
            tempSet.erase(s[left]); //移除左边界的字符
            left++;
        }
    }
    return res;
}
/**
 * 给定一个字符串，求最长回文(正读倒读都一样)子串
 */
string longestPalindrome(string s) {
     int len = s.length();
    //dp[j][i]为true时表示索引j到索引i形成的子串为回文子串，且子串起点索引为j,长度为i - j + 1
    bool ** dp = new bool*[len];
    for(int i = 0; i < len; i++) {   //为指针数组的每个元素分配一个数组
        dp[i] = new bool[len];
        *dp[i] = false;
    }
    int maxlen = 1;     //保存最长回文子串长度
    int start = 0;      //保存最长回文子串起点
    for(int i = 0;i < len; ++i){
        for(int j = 0; j<=i; ++j){
            if(i - j < 2){
                dp[j][i] = (s[i] == s[j]);
            }else{
                dp[j][i] = (s[i] == s[j] && dp[j+1][i-1]);
            }
            if(dp[j][i] && maxlen < (i-j+1)){
                maxlen = i-j+1;
                start =j;
            }
        }
    }
    for(int i = 0; i < len; ++i){
        delete []dp[i];
    }
    delete []dp;
    return s.substr(start, maxlen);
}


void test49_1(){
    string s = "abcabcbb";
    int len = lengthOfLongestSubstring(s);
    cout << len;
}
void test49_2(){
    string s = "aaaa";
    string s2 = longestPalindrome(s);
    cout << s2;
}


int main49(){
   // test49_1();
    test49_2();
    return 0;
}
